package com.zhugang.week08;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: solveNQueen
 * @author: chanzhugang
 * @create: 2022/08/04 15:43
 */
public class SolveNQueens2 {

    /**
     * 面试题 08.12 八皇后
     *
     * @param n
     * @return
     */

    private List<List<String>> result = new ArrayList<>();

    public List<List<String>> solveNQueen(int n) {
        // 回溯模版
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        backtrack(0, board, n);
        return result;
    }

    /**
     * @param row   阶段
     * @param board path
     * @param n
     */
    private void backtrack(int row, char[][] board, int n) {
        if (row == n) {
            // 结束条件，得到可行解
            List<String> snapshot = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                snapshot.add(new String(board[i]));
            }
            result.add(snapshot);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isOk(board, n, row, col)) {
                board[row][col] = 'Q';

                backtrack(row + 1, board, n);
                board[row][col] = '.';
            }
        }
    }

    /**
     * row行col列放置是否合适
     *
     * @param board
     * @param n
     * @param row
     * @param col
     * @return
     */
    private boolean isOk(char[][] board, int n, int row, int col) {
        for (int i = 0; i < n; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        int i = row - 1;
        int j = col + 1;
        while (i >= 0 && j < n) {
            if (board[i][j] == 'Q') {
                return false;
            }
            i--;
            j++;
        }

        i = row - 1;
        j = col - 1;
        while (i >= 0 && j >= 0) {
            if (board[i][j] == 'Q') {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
}